package day05;

import java.util.List;

/**
 * leetcode 3350
 * 给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增 子数组。
 * 具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：
 * 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
 * 这两个子数组必须是 相邻的，即 b = a + k。
 * 返回 k 的 最大可能 值。
 */

public class MaxIncreasingSubarrays {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int len = nums.size();

        // 记录子串个数
        int subCount = 0;
        // 记录子串最大长度
        int maxSubLen = 0;
        // 记录严格递增子串的起始位置和长度；
        int[][] subarrayLen = new int[len+1][2];

        subarrayLen[0] = new int[]{0, 1};

        // 遍历数组，识别所有连续的严格递增子序列
        for(int i=1; i < len; i++){
            if(nums.get(i) > nums.get(i - 1)) subarrayLen[subCount][1]++;
            else{
                maxSubLen = Math.max(maxSubLen, subarrayLen[subCount][1]);
                subarrayLen[++subCount] = new int[]{i,1};
            }
        }
        maxSubLen = Math.max(maxSubLen, subarrayLen[subCount][1]);

        // 计算相邻递增子序列间可形成的最大交错序列长度
        int maxK = maxSubLen / 2;
        for(int i=0; i<subCount; i++){
            if(subarrayLen[i][0] + subarrayLen[i][1] == subarrayLen[i+1][0]){
                int nowK = Math.min(subarrayLen[i][1], subarrayLen[i + 1][1]);
                maxK = Math.max(maxK, nowK);
            }
        }
        return maxK;
    }
}
